#include <stdio.h>
#include <stdlib.h>

#define kMaxSize 1000001
#define NIL -1

typedef int Position;
typedef struct StringNode *String;
struct StringNode {
    char data[kMaxSize]; /* 存储字符的数组 */
    int length; /* 字符串长度 */
};

String InitStr() {
    /* 初始化一个空的字符串 */
    String s;

    s = (String)malloc(sizeof(struct StringNode));
    s->length = 0;

    return s;
}

int Hash(String s, Position start, int len, int pre_hash_val) {
    /* 根据前次计算出的 pre_hash_val 值，滚动计算散列值 */
    /* pre_hash_val<0 则从start计算len个字符的散列值 */
    int hash_val, i;

    if (pre_hash_val >= 0) {
        hash_val = pre_hash_val - s->data[start - 1] + s->data[start + len - 1];
    } else { /* 从start计算len个字符的散列值 */
        hash_val = 0;
        for (i = 0; i < len; i++) {
            hash_val += s->data[start + i];
        }
    }
    return hash_val;
}
/* 算法4-15：字符串模式匹配的KR算法 PatternMatchKR(s,t) */
Position PatternMatchKR(String s, String t) {
    int n, m, i, j;
    int ht, hs;
    Position p;

    n = s->length;
    m = t->length;
    ht = Hash(t, 0, m, -1); /* 计算t的散列值 */
    p = NIL;
    hs = -1;
    for (i = 0; i <= (n - m); i++) {
        hs = Hash(s, i, m,
                  hs); /* 主串s以i为第一个位置、长度为m的散列值 */
        if (hs == ht) { /* 当散列值相等时 */
            j = 0;
            while ((j < m) && (s->data[i + j] == t->data[j])) {
                j++; /* 检查子串是否真的匹配 */
            }
            if (j == m) {
                p = i; /* 匹配成功 */
                break;
            }
        } /* 若散列值不相等则直接跳过 */
    }
    return p;
}
/* 算法4-15 结束 */

String ReadString() {
    int i;
    String s;

    s = InitStr(); /* 创建空的字符串 */
    i = 0;
    s->data[i] = getchar();
    while (s->data[i] != '\n') {
        i++;
        s->data[i] = getchar();
    }
    s->data[i] = '\0'; /* 字符串结束符占1位 */
    s->length = i;
    return s;
}

int main(void) {
    String s, t;
    Position p;

    s = ReadString();
    t = ReadString();
    p = PatternMatchKR(s, t);
    if (p != NIL)
        printf("%s\n", s->data + p);
    else
        printf("匹配失败。\n");

    return 0;
}